#include "./sortdatatype.h"

// 直接排序
/**
 * 思想：假设待排序数组 R[1..n], 在排序过程某一时刻, R 被划分为两个子区间: R[1..i-1] 和 R[i..n].
 * 其中前个为已排好的有序区,后个为无序区. 开始时, 有序区只含元素R[1], 无序区为R[2..n]
 * 排序过程 只需每次从无序区取出第一个元素, 然后插入到有序合适的位置, 使之称为新的有序区, 依次n-1次插入
 *
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N)
 */
void directInsertSort(SeqList R, int len)
{
    RecType temp;
    // 需要插入 n-1 次, 【有序区】-【无序区】
    for (int i = 1; i < len; i++)
    {
        // 每次插入更新 无序区开始下标
        int j = i;
        // 取无序区的元素
        temp = R[j];
        // 若无序元素小于有序区最后一个元素, 若满足则循环遍历将元素插入有序区
        while (j > 0 && temp.key < R[j - 1].key)
        {
            R[j] = R[j - 1];
            j--;
        }
        R[j] = temp;
        printf("==>i=%d, array=", i);
        printSeqList(R, len);
    }
}

// 希尔排序(缩小增量排序) 是直接插入排序的一种优化排序算法
/**
 * 思想: 将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,
 * 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小)时, 再对全体元素进行一次直接插入排序
 *
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N^1.3)
 */
void shellInsertSort(SeqList R, int len)
{
    RecType temp;
    // 步长初始化为数组长度的一半，每次遍历后步长减半,
    int step = (len -1)/ 2;
    while (step > 0)
    {
        printf("---------->step: %d, array: ", step);
        printSeqList(R, len);

        // 直接插入排序
        for (int i = step; i < len; i++)
        {
            temp = R[i];
            int k = i;
            printf("---------k=%d, temp=%d\n", k, temp.key);
            while (k >= step && temp.key < R[k - step].key)
            {
                printf("   --[%d - %d ]\n", temp.key ,R[k - step].key);
                R[k] = R[k - step];
                printf("\t");
                printSeqList(R, len);

                k -= step;
            }
            // 有序时也会执行这步
            R[k] = temp;
            printf("==>i=%d, array=[", i);
            printSeqList(R, len);
        }

        step /= 2;
    }
}

/**
 * 插入排序
 *
 * 时间复杂度为 O(N^2)
 * 空间复杂度为 O(1)
 *
 * 最坏情况时间复杂度为 O(N^2)
 * 最佳情况的时间复杂度为 O(N)
 */
void insertionSort(int arr[], int len)
{
    int key, j;
    for (int i = 1; i < len; i++)
    {
        key = arr[i];
        j = i - 1;

        while (j >= 0 && arr[j] > key)
        {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main()
{
    // int arr[] = {46, 39, 17, 23, 28, 55, 18, 46};
    int arr[] = {15, 16, 4, 12, 21, 23, 43, 31, 16, 13};
    int len = sizeof(arr) / sizeof(arr[0]);
    SeqList R;
    init(R, arr, len);
    printf("-------------directInsertSort---------------\n");
    directInsertSort(R, len);
    printSeqList(R, len);

    init(R, arr, len);
    printf("-------------shellInsertSort---------------\n");
    shellInsertSort(R, len);
    printSeqList(R, len);

    printf("\n-------------insertionSort---------------");
    insertionSort(arr, len);
    printArray(arr, len);

    return 0;
}
